package com.wxg.algorithm.chapter07;

import java.util.ArrayList;
import java.util.List;

public class SparseGraph {
    private int n;
    private int m;
    private boolean directed;
    private List<Integer>[] g;

    public SparseGraph( int n, boolean directed ){
        this.n = n;
        this.m = 0;
        this.directed = directed;
        g = new List[n]; // 这里不能指定泛型, 语法是这样的, 实际上只能放入 Integer
        for (int i = 0; i < n; i++){
            g[i] = new ArrayList<>();
        }
    }

    public int V(){
        return n;
    }

    public int E(){
        return m;
    }

    public void addEdge( int v, int w ){
        if ( v >=0 && v < n && w >=0 && w < n ){
            g[v].add(w);
            if ( v != w && !directed ){
                g[w].add(v);
            }

            m ++;
        }
    }

    public boolean hasEdge( int v, int w ){
        if ( v >=0 && v < n && w >=0 && w < n ){
            for ( int i = 0 ; i < g[v].size() ; i ++ ){
                if ( g[v].get(i) == w ){
                    return true;
                }
            }
            return false;
        }

        throw new RuntimeException("参数错误");
    }

    public Iterable<Integer> adj( int v ) {
        if ( v >= 0 && v < n ){
            return g[v];
        }

        throw new RuntimeException("参数错误");
    }
}
